1. Technical Field
This invention generally relates to genetic algorithms, information encoding and information encryption. Specifically, this invention relates to a methodology for encoding the complete volumetric information of a virtual object and the retrieval of same. The invention is particularly applicable to the range of problems wherein a more natural genetic-like implementation of the conventional genetic algorithm, the increased efficiency of information encoding in the form of synthetic genes and/or encryption of information utilizing synthetic genes may be found as a solution to these problems.
2. Background
Genetic algorithms have been used for decades for solving problems in many fields of research, development and implementation, most notably, the sciences and engineering. A central appeal of genetic algorithms has been the notion of novel solutions to otherwise intractable problems. For many of the same reasons that great fascination and often amazement exists for natural biological genetics, researchers have often found unique and unexpected solutions to various problem sets through the use of genetic algorithms.
In large part, genetic algorithms possess their power and effectiveness precisely because they mimic a process that, by the reckoning of current science, has been replaying itself successfully for billions of years.
Therefor, it would be desirable to provide a higher degree of transcription of natural genetic principles and apply this to the field of genetic algorithms.
As technological advances create increased opportunities for data utilization and visualization, so too are there increased strains on the prior art of encoding and retrieving such information. In particular, the field of three dimensionally viewed objects and their manipulation in digital environments have become increasingly important in medicine, education and science. Virtual reality is fast becoming an accepted, and in some cases the only, means of achieving effective communication, education and simulation. Unfortunately, information current methods of information encoding are largely inefficient and cumbersome.
Therefor, it would be desirable to provide more efficient and compact method of information encoding.
Because of exponentially increasing digital traffic, both on and off the internet, the need for totally secure forms of information exchange has become paramount. With the advent of ever more powerful computers available to almost everyone, computing intensive algorithms for data encryption, as well as the decoding of such encryption, have now become practically feasible.
The rapid rise of technical tools, more common place expertise, and the sheer power of readily available computers have spawned a new class of users whose motives are not always honorable. xe2x80x9cCode crackingxe2x80x9d and computer xe2x80x9chackingxe2x80x9d in general have become new avenues for entertainment, achievement and criminal activity. To date, very few, if any, absolutely secure information encryption algorithms exist.
Genetic algorithms are generally parallel processes that develop populations of individual data objects, usually developing binary character strings into new populations of the same data type, using methods that mimic biological genetics, such as recombination, or crossover, and a proportional reproductive schema based on the notion of Darwin""s survival of the fittest. Such algorithms start with some initial population of data objects, usually created in some pseudo random fashion. These data objects are then evaluated iteratively for fitness as it pertains to the problem at hand and genetic like operations are performed on various data objects within the population to evolve a new population.
John Holland of the University of Michigan developed the initial concept of genetic algorithms for fixed-length binary character strings in Adaptation in Artificial and Natural Systems, by Professor John H. Holland, 1975. Subsequent and significant works in genetic algorithms and genetic classifier systems may be referenced in Grefenstette, Proceedings of the Second International Conference on Genetic Algorithms, 1987; M. Srinivas, et al., xe2x80x9cGenetic Algorithms: A Surveyxe2x80x9d, Computer, vol. 27, No. 6, pages 17-26, June 1994; Goldberg, Genetic Algorithms, pages 10-20, 80-139, Addison Wesley 1989; W. B. Dress, xe2x80x9cDarwinian Optimization of Synthetic Neural Systemsxe2x80x9d, IEEE First International Conference on Neural Networks, San Diego, June 1987, vol. No. 3, pages 769 775; Schaffer et al., An Adaptive Crossover Distribution Mechanism for Genetic Algorithms, Proceedings of the 2nd International Conference on Genetic Algorithms, Jul. 28-31, 1987, pages 36-40; and Melanie Mitchell, xe2x80x9cAn Introduction to Genetic Algorithmsxe2x80x9d, pages 87-113, MIT Press 1996.
Several improvements have been made to Holland""s basic premise over the ensuing years, but none has addressed the lack of parallelism between these genetic algorithms and their natural genetic paradigm, namely that in conventional genetic algorithms, sexual-like recombination or crossover, regardless of its geometry or relative sophistication, occurs on a population member or data object only in its final form, that is its phenotypical form. This is the biological equivalent, for example, of grafting the legs of a very fast runner onto the body of a person having great upper body strength in order to achieve some environmental fitness objective.
Indeed, all efforts toward improvements in genetic algorithms have been made on the same plane. That is to say, the prior art procedures of crossover and fitness selection in genetic algorithms, regardless of their variations, are performed on the same level of member development, without regard for the complexities surrounding the integrated behavior of the genomic regulatory systems underlying ontogeny, or in other words, the unfolding of events involved in an organism changing gradually from a simple to a more complex level.
In reality, biological sexual recombination occurs at the genotypical level, where the genotype is a group of organisms sharing a specific genetic constitution. The phenotype, the constitution of an organism as determined by the interaction of its genetic constitution and the environment, is the phase in the overall scheme of things where natural selection occurs.
In fact, the two procedures, biological crossover or sexual recombination and fitness selection, occur not only at very different levels but on an incredibly different scale.
xe2x80x9cIt has been estimated that the sperm that fertilized all the eggs from which the present human population of the world developed could be packed into a container smaller than an eraser on a pencil the biologically inherited qualities of human beingsxe2x80x94the similarities as well as the differences that distinguish one human from another and from all other living thingsxe2x80x94have their basis in a minute mass of sperm . . . xe2x80x9c.Adrian M. Srb, xe2x80x9cGeneral Geneticsxe2x80x9d, pages 2-26, 265-384, W. H. Freeman and Company 1965.
Volume rendering is a computer graphics technique whereby the object or phenomenon of interest is sampled or subdivided into many cubic building blocks, called voxels, or volume elements. A voxel is the three dimensional (hereafter 3-D) counterpart of the two dimensional (hereafter 2-D) pixel and is a measure of unit volume. Each voxel carries one or more values for some measured or calculated property of the volume and is typically represented by a unit cube. The 3-D voxel sets are assembled from multiple 2-D images, and are displayed by projecting these images into 2-D pixel space where they are stored in a frame buffer. Volumes rendered in this manner have been likened to a translucent suspension of particles in 3-D space.
In surface rendering, the volumetric data must first be converted into geometric primitives, by a process such as isosurfacing, isocontouring, surface extraction or border following. These primitives, such as polygon meshes or contours, are then rendered for display using conventional geometric rendering techniques. Both techniques have advantages and pitfalls.
A major advantage of the volume rendering technique is that the 3-D volume can be displayed without any knowledge of the geometry of the data set and hence without intermediate conversion to a surface representation. This conversion step in surface rendering can sometimes be quite complex, especially if surfaces are not well defined, e.g. noisy 2-D images, and can require a lot of user intervention, such as manual contour tracing.
On the other hand, because the 3-D data set is reduced to a set of geometric primitives in surface rendering, this can result in a significant reduction in the amount of data to be stored, and can provide fast display and manipulation of the 3-D reconstructions produced by this method.
By contrast, since all of the image stack data is used for volume rendering, computers with lots of memory and processing power are required to handle volumes rendered in this manner. Because the entire data set is preserved in volume rendering, any part, including internal structures and details, which may be lost when reducing to geometric structures with surface rendering, may be viewed.
Since most applications of interest wish to preserve the internal structures and details resulting from volume rendering, but would desire to perform more efficiently, particularly with massive amounts of data, as in the case of surface rendering, it would be highly desirable to provide a technique that achieved the advantages of both methods, that is, the speed of surface rendering with the detail of volume rendering.
The prior art of data encryption is at least two thousand years old and the entire field of cryptology has evolved to a very high degree of specialization. The most commonly used methods employ a xe2x80x9ckeyxe2x80x9d or system of keys. A key may be a binary equivalent of a phrase, e.g.xe2x80x94xe2x80x9cthe quick brown foxxe2x80x9d. This binary number is in turn used to encrypt an information data set. As a general rule, the longer the binary number, the more difficult it is to break into an encrypted message. Thus, so-called xe2x80x9cstrongxe2x80x9d encryption algorithms might use a 128 bit method in contrast to a more standard 40 bit method. One form of early key-encryption algorithms was the xe2x80x9csymmetricxe2x80x9d key approach. Symmetric key encryption methods require that both the sender and receiver of encrypted messages have access to the same key and that same key is used to both encrypt and decrypt, thus, xe2x80x9csymmetricxe2x80x9d. Such systems assume that those communicating have an alternative means of secure communication, otherwise there could be no means of agreement on what key(s) to use.
In 1976, Whitfield Diffie and Martin Hellman at Stanford University, proposed the xe2x80x9cpublic keyxe2x80x9d encryption system. The system was soon named xe2x80x9cRSAxe2x80x9d. A user""s RSA software generates a pair of keys. Each is a large integer, sometimes more than 500 digits. The two keys are mathematically related. Either key can be input into certain software to encrypt a message, and the other key can be input later to decrypt the same message. That is, encrypt with one key and decrypt with another. In practice, however, RSA encryption is used more as a security xe2x80x9cenvelopexe2x80x9d. Thus, what is transmitted is a message encrypted with a symmetric key and a copy of the key used, wrapped in the RSA envelope. At the receiving end, the decryption software first unwraps the RSA envelope, obtains the symmetric key and uses that key to decode the message.
In any event the same encryption will result in each instance that the same key is used on the same information data set. That is, the process can be replicated.
Regardless of the type of key system used, symmetric, public etc., the replication is ultimately the vulnerable aspect of the prior art of information encryption.
Therefore, it would be desirable to provide an improved method for absolutely secure information encryption that can not be replicated.
The invention uses biological genetics as a metaphor to achieve a greater parallel with the natural genetic paradigm by incorporating synthetic genes into the genetic algorithmic process. Employing synthetic genes within the structure of computer readable memory provides increased flexibility and power to genetic algorithms, allows for efficient and compact information encoding, provides secure information encryption, and provides a problem solving tool which can be applied to a large number of very diverse problems.
Another embodiment of the invention provides a method and system for describing the volumetric detail of a virtual object by encoding the surface employing synthetic genes.
Yet another embodiment of the invention provides a method and system using synthetic genes which is completely non-replicative.
Additional advantages and novel features of the invention will be set forth in part in the description that follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention.